package 剑指offer;

import java.util.Arrays;

/**
 * @author zhangmin
 * @create 2021-12-03 11:28
 * 数学（简单）
 */
public class day23_39_66 {

    /**===========================================================================================================================
     * 剑指 Offer 39. 数组中出现次数超过一半的数字
     * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可以假设数组是非空的，并且给定的数组总是存在多数元素。
     * 1、map记录每个元素出现的次数，并每次判断，当有一个数字出现次数超过一半即可返回
     * 2、对数组进行排序，有序的数组的中间元素即为结果   O(nlogn)
     * 3、随机，有一大半的元素下标是众数，所有随机取一个下标判断是否是众数 --  期望的时间复杂度为 O(n)  最坏是无穷大
     * 4、分治：如果数 a 是数组 nums 的众数，如果我们将 nums 分成两部分，那么 a 必定是至少一部分的众数。 递归求解
     * 5、Boyer-Moore 投票算法:如果我们把众数记为 +1，把其他数记为 −1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。
     * */
    //5.我们维护一个候选众数 candidate 和它出现的次数 count。初始时 candidate 可以为任意值，count 为 0；
    // 我们遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x 之前，如果 count 的值为 0，我们先将 x 的值赋予 candidate，随后我们判断 x：
    // 如果 x 与 candidate 相等，那么计数器 count 的值增加 1；
    //如果 x 与 candidate 不等，那么计数器 count 的值减少 1。
    public int majorityElement1(int[] nums) {
        int count=0;
        Integer candidate=null;
        for (int i = 0; i < nums.length; i++) {
            if (count==0) {
                candidate=nums[i];
            }
            count+=(nums[i]==candidate)?1:-1;
        }
        return candidate;
    }
    //2、排序
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }

    /**===========================================================================================================================
     * 剑指 Offer 66. 构建乘积数组
     * 给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积,
     * 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。<不能使用除法></不能使用除法>。
     * 1、使用除法，算出整个数组相乘的结果，然后挨个相除
     * 2、保存一个前缀积，一个后缀积
     * */
    public int[] constructArr(int[] a) {
        int n=a.length;
        if (n==0) return new int[0];
        if (n==1) return new int[]{a[0]};
        int[] pre=new int[n];
        int[] post=new int[n];
        pre[0]=a[0];
        post[n-1]=a[n-1];
        for (int i = 1; i < n; i++) {
            pre[i]=pre[i-1]*a[i];
            post[n-i-1]=post[n-i]*a[n-i-1];
        }
        int[] b=new int[n];
        b[0]=post[1];b[n-1]=pre[n-2];
        for (int i = 1; i < n-1; i++) {
            b[i]=pre[i-1]*post[i+1];
        }
        return b;
    }

}
